13.3 Multidimensional Scaling and Seriation

165

measure of the distance between the distance matrix estimate and the given distance

matrix vectors). Iteration continues until a defined minimum of the stress function is

found; a representation of the original upper MM-dimensional space of upper NN vectors may then

be displayed from the estimated vectors.

Theory. Define the upper MM-dimensional vector space of upper NN objects by the vectors

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutxi =

M

Σ

μ=1

biμ ˆyμ ,

(13.11)

where ModifyingAbove y With caret Subscript mu ˆyμ are the unit vectors of the space. The Euclidean distances between these

vectors are then given by the upper N times upper NN × N distance matrix

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutEi j = [(xi −x j)²]^1/2 .

(13.12)

If only this matrix is known and not the underlying vectors, then an estimated distance

matrix may be defined:

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout^∼Ei j = [(∼xi −∼x j)²]^1/2 .

(13.13)

The estimated vectors may be formed as

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout∼xi =

∼

M

Σ

μ=1

aiμ ˆyμ ,

(13.14)

where

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutaiμ = a0iμ + ziμ

(13.15)

anda Subscript 0 i mua0iμ are initial values selected at random andz Subscript i muziμ are used to propagate the vector

through iteration.

The stress functionupper SS is a normalized measure of the distance between the distance

matrix estimate and the given distance matrix vectors:

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutS² =

ΣN,N

i, j=1^{[∼Ei j −Ei j]2}

ΣN,N

i, j=1 ^{Ei j}

.

(13.16)

This may be minimized by

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayout ^∂S2

∂zkμ

= 0 ,

(13.17)

but upper E Subscript i jEi j is constant and given by

StartLayout 1st Row 1st Column r Subscript n minus 2 2nd Column equals 3rd Column r Subscript n minus 1 Baseline q Subscript n minus 1 Baseline plus r Subscript n Baseline comma 2nd Row 1st Column Blank 3rd Row 1st Column r Subscript n minus 1 2nd Column equals 3rd Column r Subscript n Baseline q Subscript n Baseline comma EndLayoutB =

N,N

Σ

i, j=1

Ei j ,

(13.18)